package com.lz.learning;

import java.util.Arrays;

public class Envelope {
    public static void main(String[] args) {

    }

    /**
     * 信封嵌套问题就需要先按特定的规则排序，之后就转换为一个 最长递增子序列问题，可以用前文 二分查找详解 的技巧来解决了。
     * <p>
     * 宽w 搞h
     * 按照宽排序，若相同
     * 在解决多维问题，均可以采用该种方法
     * <p>
     * NOTE: 则按照h倒序,求h的最长子序列
     *
     * @param array
     * @return
     */
    int maxEvenlope(int[][] array) {
        Arrays.sort(array, (a, b) ->
                a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]
        );
        int[] h = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            h[i] = array[0][i];
        }
        return maxChildSequence(h);
    }


    int maxChildSequence(int[] array) {
        if (array.length < 1) return 0;
        // 后一个数比前一个数大
        int[] dp = new int[array.length];
        Arrays.fill(dp, 1);

        int max = -1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                if (array[i] > array[j]) {
                    dp[i] = (dp[j] + 1);
                    max = max > dp[i] ? max : dp[i];
                }

            }
        }
        System.out.println(max);
        return max;

    }
}
